package codeTop;

public class q32 {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int dp[] = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (i>0&&i-1>=dp[i-1]){
                    if (s.charAt(i - dp[i - 1]-1) == '(') {
                        dp[i] += dp[i-1]+2;
                        if (i - dp[i - 1] - 2 >= 0) {
                            dp[i]+=dp[i-dp[i-1]-2];
                        }
                    }
                }
                max = Math.max(max,dp[i]);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        q32 q = new q32();
        q.longestValidParentheses("(()");
    }
}
